/* 
 * File:   main.cpp
 * Author: jocker
 *
 * Created on 9. April 2011, 02:05
 */
#include <cstdlib>
#include <iostream>
#include <vector>
#include <ctime>
#include <algorithm>
#include <cmath>
using namespace std;

/*  We use this function each time we remove the root node, to restructure the
 heap evenly.
 */
template <class T>
void createData(vector<T> &list, int size) {
    int lBound = 0, hBound = 1000;
    T num;
    int range = hBound - lBound + 1;
    for (int i = 0; i < size; i++) {
        num = lBound + int(rand() / (RAND_MAX / range + 1.0));
        list.push_back(num);
    }
}

template <class T>
void fixHeap(vector<T> &list, int root, int key, int bound) {
    //list  the list/heap being sorted
    //root  the index of the root of the heap
    //key   the key value that needs to be reinserted in the heap (the one that was
    // taken from the tree's bottom )
    //bound the upper limit (index) on the heap (or list size)
    int vacant = root;
    int largerChild;
    while (2 * vacant <= bound) {
        largerChild = 2 * vacant;
        if (largerChild < bound && list[largerChild + 1] > list[largerChild])
            largerChild++;
        //does the key belong above this child?
        if (key > list[largerChild])break;
        else // no, move the larger child up
        {
            list[vacant] = list[largerChild];
            vacant = largerChild;
        }
    }
    list[vacant] = key;
}

template<class T>
void shiftHeapUp(vector<T> &list, int rootPos, int key, int vacantPos) {
    //key -> element to be inserted into the vacant position
    //vacantPos -> the position that can be occupied by key and is currently
    //              available
    if (vacantPos == rootPos)
        list[vacantPos] = key;
    else {
        int fatherPos = vacantPos / 2;
        if (key <= list[fatherPos]) {
            list[vacantPos] = key;
        } else {
            list[vacantPos] = list[fatherPos];
            shiftHeapUp(list, rootPos, key, fatherPos);
        }
    }
}

template <class T>
void fixHeapModified(vector<T> &list, int root, int key, int bound) {
    //list  the list/heap being sorted
    //root  the index of the root of the heap
    //key   the key value that needs to be reinserted in the heap (the one that was
    // taken from the tree's bottom )
    //bound the upper limit (index) on the heap (or list size)
    int vacant = root;
    int largerChild;
    while (2 * vacant <= bound) {
        largerChild = 2 * vacant;
        if (largerChild < bound && list[largerChild + 1] > list[largerChild])
            largerChild++;
        //does the key belong above this child?
        shiftHeapUp(list,root,list[largerChild],vacant);
            vacant = largerChild;
    }
    list[vacant] = key;
}

void execSimpleHeapSort(int size,bool printResult) {
    int max;
    vector<int> list;
    createData(list,size);
    const int N = list.size() - 1;
    //to create the heap structure
    for (int i = N / 2; i >= 1; i--) {
        fixHeap(list, i, list[i], N - 1);
    }
    //here we remove the root element (the maximum value) N times
    //and of course we need to fix the heap each time we do that
    for (int i = N - 1; i > 1; i--) {
        max = list[1];
        fixHeap(list, 1, list[i], i - 1);
        list[i] = max;
    }

    if(printResult){
    cout << " The sorted list : " << endl;
    for (int i = 1; i < N; i++) {
        cout << list[i] << " ";
    }
    cout << endl;
    }


}

void execModifiedHeapSort(int size,bool printResult) {
    int max;
    vector<int> list;
    createData(list,size);
    const int N = list.size() - 1;
    //to create the heap structure
    for (int i = N / 2; i >= 1; i--) {
        fixHeap(list, i, list[i], N - 1);
    }
    //here we remove the root element (the maximum value) N times
    //and of course we need to fix the heap each time we do that
    for (int i = N; i > 1; i--) {
        max = list[1];
        fixHeapModified(list, 1, list[i], i - 1);
        list[i] = max;
    }

    if(printResult){
    cout << " The sorted list : " << endl;
    for (int i = 1; i < N; i++) {
        cout << list[i] << " ";
    }
    cout << endl;
    }
}

void simpleSTLsort(int size){
    vector<int> list;
    createData(list,size);
    sort(list.begin(),list.end());
}



template<class T>
int promote(vector<T> &list, int heightStop, int vacant, int h){
    int vacantStop;
    if( h<= heightStop) vacantStop = vacant;
    else if(list[2*vacant] <= list[2*vacant+1]){
        list[vacant] = list[2*vacant+1];
        vacantStop = promote(list,heightStop, 2*vacant+1, h-1);
    }
    else{
        list[vacant] = list[2*vacant];
        vacantStop = promote(list,heightStop, 2 * vacant, h-1);
    }
return vacantStop;
}

template<class T>
void fixHeapFast(vector<T> &list, int n, int key, int vacant, int h  ){
    if(h<= 1){

    }
    else{
        int heightStop = h/2;
        int vacantStop = promote(list,heightStop,vacant,h);
        // vacantStop is the new vacant position, at height heightStop
        int vacantsFather = vacantStop /2;
        if(list[vacantsFather] <= key){
            list[vacantStop] = list[vacantsFather];
            shiftHeapUp(list,vacant,key,vacantsFather);
        }
        else
            fixHeapFast(list,n,key, vacantStop, heightStop);

    }
}

void execFastHeapSort(int size,bool printResult) {
    int max;
    vector<int> list;
    createData(list,size);
    const int N = list.size() - 1;
        cout << " Created data : " << endl;
    for (int i = 1; i < N; i++) {
        cout << list[i] << " ";
    }
    cout << endl;
    
    //to create the heap structure
    for (int i = (N-1); i >= 2; i--) {
        int h = (int)ceil(log(i+1))-1;
        int max = list[1];
        int k = list[i];
        //fixHeap(list, i, list[i], N - 1);
        fixHeapFast(list,i-1,k,1,h);
        list[i] = max;
    }
    //here we remove the root element (the maximum value) N times
    //and of course we need to fix the heap each time we do that
//    for (int i = N - 1; i >= 1; i--) {
//        max = list[1];
//        int h = (int)ceil(log(i+1))-1;
//        //cout<<"h: "<<h<<endl;
//        fixHeapFast(list,N-1,list[i],1,h);
//        list[i] = max;
//    }

    if(printResult){
    cout << " The sorted list : " << endl;
    for (int i = 1; i < N; i++) {
        cout << list[i] << " ";
    }
    cout << endl;
    }


}

int main(int argc, char** argv) {
    srand((unsigned) time(0));
    //execImprovedHeapSort(10000000,false);
    //execSimpleHeapSort(10000000,false);
    execFastHeapSort(10,true);
    //simpleSTLsort(100000000);
    return 0;
}


